package com.cat.dataStructure02;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/valid-parenthesis-string/
 * @create 2025/10/26 16:23
 * @since JDK17
 */

public class Solution62 {
    public boolean checkValidString(String s) {
        Deque<Integer> left = new ArrayDeque<>(), star = new ArrayDeque<>();
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {    //
                left.addLast(i);
            } else if (arr[i] == ')') {
                if (!left.isEmpty()) {
                    left.pollLast();
                } else if (!star.isEmpty()) {
                    star.pollFirst();
                } else {
                    return false;
                }
            } else {
                star.addLast(i);
            }
        }
        while (!left.isEmpty()) {
            if (star.isEmpty() || left.pollLast() > star.pollLast()) {
                return false;
            }
        }

        return true;
    }
}
